/**
 * 给定两个十进制数字字符串L和R，再给定一个进制b
 * 求[L, R]区间内满足b进制表示数位非递减的数的数量
 * 答案对1E9+7取模
 * 在分解数字之前要做一个进制转换
 */
using llt = long long;
llt const MOD = 1E9 + 7;

int Base;
vector<int> G;
// Dij表示搜索到i位前一位数字为j的目标
// 注意可能有二进制，log10(2)比0.3稍大一点
// 因此100位十进制大约是333位二进制
llt D[350][10];
llt dfs(int pos, int pre, bool lead, bool limit){
    if(-1 == pos) {
        return 1;
    }
    if(not lead and not limit and -1 != D[pos][pre]) {
        return D[pos][pre];
    }
    int last = limit ? G[pos] : Base - 1;
    llt ans = 0;
    for(int i=0;i<=last;++i){
        if(i < pre) continue;
        ans += dfs(pos - 1, i, lead&&0==i, limit&&last==i);
        ans %= MOD;
    }
    if(not lead and not limit){
        D[pos][pre] = ans;
    }    
    return ans;
}

llt digitDP(const string & s){
    vector<int> vec;
    G.clear();
    for(auto c : s) vec.emplace_back(c - '0');
    reverse(vec.begin(), vec.end());
    // 做进制转换
    while(vec.size() > 1 or vec[0] != 0){
        vector<int> tmp;
        int r = 0;
        int n = vec.size();
        for(int i=n-1;i>=0;--i){
            auto cur = r * 10 + vec[i];
            r = cur % Base;
            tmp.emplace_back(cur / Base);
        }
        G.emplace_back(r);
        reverse(tmp.begin(), tmp.end());
        while(tmp.size() > 1 and tmp.back() == 0) tmp.pop_back();
        vec.swap(tmp);
    }
    return dfs(G.size()-1, 0, true, true);
}

class Solution {
public:
    int countNumbers(string l, string r, int b) {
        memset(D, -1, sizeof(D));
        Base = b;

        // 先把l减减
        this->dec(l);
        if(l.empty()) return digitDP(r);
        return ((digitDP(r) - digitDP(l)) % MOD + MOD) % MOD;
    }
    void dec(string & s){
        int k = s.length() - 1;
        while(k >= 0 and s[k] == '0') --k;
        if(-1 == k) return s.clear();
        
        s[k] -= 1;
        for(int i=k+1;i<s.length();++i) s[i] = '9';
        return;
    }
};
